package com.sam;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * 六种面额 1、5、10、20、50、100 元的纸币，假设每种币值的数量都足够多，编写程序求组成N元（N为0~10000的非负整数）的不同组合的个数
 */
public class GiveChange {
    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            System.out.println(countChange(i));

        }
        List<int[]> list = new ArrayList<>();
        list.add(new int[]{1, 2});
        for (int i = list.size()-1; i >=0; i++) {

        }


    }

    public final static int[] BILL = {1, 2, 10, 20, 50, 100};

    //组成N元的方法数
    public static int countChange(int n) {
        int[] temp = new int[n+1];
        temp[0] = 1;
        int current;

        for (int i = 1; i <= n; i++) {//钱=i+1
            current = 0;
            for (int j = 0; j < BILL.length; j++) {
                if (i - BILL[j] >= 0) {
                    current += temp[i - BILL[j]];
                }
            }
            temp[i] = current;

        }
        return temp[n];
    }
}
